# 问题简化，10000个数字中找最大1000个

class InsertTopn
  DEFAULT_BLOCK = proc {|a, b| a <=> b}
  DEFAULT_SIZE = 10

  attr_accessor :nums, :max_size, :compare_proc

  def initialize(max_size = DEFAULT_SIZE, &block)
    @nums, @max_size = [], max_size
    @compare_proc = block || DEFAULT_BLOCK
  end

  def push(values)
    Array(values).each do |value|
      push_single(value)
      puts "#{value}\t#{nums.inspect}"
    end
    self
  end

  def index(value)
    left, right = 0, nums.size.pred

    while left <= right
      mid = (left + right) / 2
      mid_value = nums[mid]

      case compare_proc.call(mid_value, value)
      when -1
        left = mid.next
      when 1
        right = mid.pred
      else
        return nil
      end
    end
    left
  end

  private

  def push_single(value)
    idx = index(value)

    return self if idx.nil?

    if full?
      if idx > 0
        @nums.insert(idx, value)
        @nums.shift
      end
    else
      @nums.insert(idx, value)
    end
    self
  end

  def full?
    nums.size >= max_size
  end
end
